import javax.xml.crypto.Data;
import java.util.ArrayList;
import java.util.List;

/**
 * 堆数据结构：1、是一颗完全二叉树；2、父节点必须比子节点大或者小
 * 如果父节点比子节点大：最大堆
 * 如果父节点比子节点小：最小堆
 * 本类实现一个用数组实现的最大堆
 * 17
 * /  \
 * 12    5
 * /  \  / \
 * 8   11 3   4
 * /\   /\
 * 7  1 10 9
 *
 * @author HuRui
 * create on 2018/12/24 9:43
 */
public class MaxHeap {

    protected List<Comparable> comparableList;
    protected int count;

    /**
     * init a ArrayList size=capacity+1,because first index is null,we will begin in second index.
     *
     * @param capacity init capacity
     */
    public MaxHeap(int capacity) {
        comparableList = new ArrayList<>(capacity + 1);
        comparableList.add(null);
        count = 0;
    }

    /**
     * Returns <tt>true</tt> if this list contains no elements.
     *
     * @return <tt>true</tt> if this list contains no elements
     */
    public boolean isEmpty() {
        return count == 0;
    }

    /**
     * Returns the number of elements in this collection.  If this collection
     * contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
     * <tt>Integer.MAX_VALUE</tt>.
     *
     * @return the number of elements in this collection
     */
    public int size() {
        return count;
    }

    /**
     * add element
     *
     * @param element element
     * @return this index of this element position
     */
    public int add(Comparable element) {
        count++;
        if (count == 0) {
            this.comparableList.add(element);
            return 1;
        }
        this.comparableList.add(element);
        //Compare to its parent element
        shiftUp(count);
        return count;
    }

    /**
     * remove first element
     *
     * @return
     */
    public Comparable remove() {
        Comparable comparable = comparableList.get(1);
        shiftDown();
        return comparable;
    }

    /**
     * get first element
     * @return first element in array
     */
    public Comparable get() {
        return comparableList.get(1);
    }

    /**
     * find the position to up
     *
     * @param index
     */
    private void shiftUp(int index) {
        while (index > 1 && comparableList.get(index / 2).compareTo(comparableList.get(index)) < 0) {
            DataUtil.swap(comparableList, index, index / 2);
            index /= 2;
        }
    }

    /**
     * find the position to down
     */
    private void shiftDown() {
        comparableList.set(1, comparableList.get(count));
        comparableList.remove(count);
        count -- ;
        int index = 1;
        while (2 * index <= count) {
            int k = 2 * index;
            if (k + 1 <= count && comparableList.get(k).compareTo(comparableList.get(k + 1)) < 0) {
                k++;
            }
            if (comparableList.get(index).compareTo(comparableList.get(k)) >= 0) {
                break;
            }
            DataUtil.swap(comparableList, index, k);
            index = k;
        }
    }
    public static void main(String[] args) {
        PrintableMaxHeap maxHeap = new PrintableMaxHeap(1000000);
        for (int i = 0; i < 1000000; i++) {
            int element = (int) (Math.random() * 1000000);
            maxHeap.add(element);
        }
//        maxHeap.treePrint();
//        Comparable remove = maxHeap.remove();
//        System.out.println("remove:" + remove);
//        maxHeap.treePrint();
        while (maxHeap.count>0) {
//            if(maxHeap.count / 500 == 0)
            System.out.print(maxHeap.remove()+",");
        }
    }
}
